package _动态规划系列._博弈问题;

/**
 * @Author: 吕庆龙
 * @Date: 2020/4/2 15:53
 * <p>
 * 功能描述:
 */
public class Summary_Game {

    /**
     * dp[i][j].fir  从piles[i...j]这些石子堆里，先手能获得的最高分
     * dp[i][j].sec  从piles[i...j]这些石子堆里，后手能获得的最高分
     */
    public int stoneGame(int[] piles) {

        int n = piles.length;
        Pair[][] dp = new Pair[n][n];

        for (int i = 0; i < n; i++)
            for (int j = i; j < n; j++)
                dp[i][j] = new Pair(0, 0);

        //base case i==j的时候  先手有piles[i]分,后手0分
        for (int i = 0; i < n; i++) {
            dp[i][i].fir = piles[i];
            dp[i][i].sec = 0;
        }

        int j = 0;
        //要斜着遍历dp table
        for (int l = 2; l <= n; l++) { //l表示斜着的层数,base case是第一层，所以这里从第2层开始
            for (int i = 0; i <= n - l; i++) {  //这个就是行标
                j = l + i - 1;

                int left = piles[i] + dp[i + 1][j].sec;  //先手选左边的石子堆
                int right = piles[j] + dp[i][j - 1].sec; //先手选右边的石子堆

                if (left > right) {
                    dp[i][j].fir = left;
                    dp[i][j].sec = dp[i + 1][j].fir;
                } else {
                    dp[i][j].fir = right;
                    dp[i][j].sec = dp[i][j - 1].fir;
                }
            }
        }
        int res = dp[0][n - 1].fir - dp[0][n - 1].sec;

        return res;
    }
}

class Pair {
    int fir, sec;

    Pair(int fir, int sec) {
        this.fir = fir;
        this.sec = sec;
    }
}